package com.gxc.tree;

/**
 * 添加与搜索单词 - 数据结构设计
 * 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 *
 * 实现词典类 WordDictionary ：
 *
 * WordDictionary() 初始化词典对象
 * void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母
 */
public class WordDictionary {

    WordDictionary[] dics;
    boolean end;

    public WordDictionary() {
        dics = new WordDictionary[26];
    }

    public void addWord(String word) {
        WordDictionary dictionary = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            int index = c - 'a';
            if (dictionary.dics[index] == null) {
                dictionary.dics[index] = new WordDictionary();
            }
            dictionary = dictionary.dics[index];
        }
        dictionary.end = true;
    }

    public boolean search(String word) {
        return search(this, word, 0);
    }

    private boolean search(WordDictionary wordDictionary, String word, int i) {
        if (wordDictionary == null) return false;
        if (i == word.length()) return wordDictionary.end;

        char c = word.charAt(i);
        int index = c - 'a';
        boolean result = false;
        if (c == '.') {
            for (int j = 0; j < wordDictionary.dics.length; j++) {
                result = search(wordDictionary.dics[j], word, i+1);
                if (result) return true;
            }
        } else {
            result = search(wordDictionary.dics[index], word, i+1);
        }
        return result;
    }
}
